The present invention is related to a method and mechanism for tracking and managing cached data in a multiprocessor system and, in particular, to a cache based vector coherency method and mechanism for tracking and managing data use in a multiprocessor system.
Present computer systems are commonly configured and function as shared multiprocessor node systems comprised of a plurality of processor nodes communicating through an interconnection structure, such as a wide or local area network or bus. Each processor node may typically be comprised of one or more processors, an input/output sub-system and a memory sub-system providing a node memory space which functionally includes both dynamic memory and storage devices such as disk drives.
One or the primary advantages of shared multiprocessor systems is that the processors may share information resident in the various processor nodes, including both data and program code. Because information is shared among the nodes and node processors, the information accessible to the processors is effectively distributed across and through the system, and the memory spaces of the processor nodes functionally form a single, global memory pool. The global memory pool and the information is typically shared at some predetermined granularity, which is often referred to as a xe2x80x9clinexe2x80x9d wherein a xe2x80x9clinexe2x80x9d is typically of a fixed size corresponding to a unit of data convenient to operations of the processors.
In a typical shared multiprocessor system, a line will reside in or be xe2x80x9cownedxe2x80x9d by one processor or node, which may change over time with operations of the system, and copies of the line may be encached in the memory space of other nodes or processors at different points in time. The processor nodes and processors will typically have rights to read, modify and write a given line or copy thereof, and these rights will vary with time, depending, for example, upon the operations of the processors. For this reason, the tracking and management of the locations and status of lines and copies of lines is a critical function of a shared multiprocessor system to allow, for example, a processor to locate a given line or copy of the line, and to insure coherency of the information as various processors utilize a line or a copy of a line.
In general, the tracking and management of lines in a shared multiprocessor system and the maintenance of information coherency requires the generation and maintenance of sharing information, that is, of information pertaining to the locations of a line and encached copies of the line, of the status of the line and the encached copies of the line, and of the rights possessed by various processors to use the line. Shared multiprocessor systems of the prior art have attempted a number of solutions to the problem of cache coherency and sharing information, all of which have been unsatisfactory for one reason or another.
One approach has been to store all of the sharing information, that is, the information pertaining to the location and status of each line and each encached copy of each line in one deterministic location, which is typically the line""s xe2x80x9chome nodexe2x80x9d. This method is advantageous in terms of performance as all of the sharing information is co-located and can therefore be processed concurrently. This method is disadvantageous, however, in requiring an excessive amount of storage overhead as each home node must maintain a xe2x80x9ctagxe2x80x9d for each of its global memory lines and each of these tags is of a relatively large size as it must contain all of the sharing information for the associated line. The end result is typically a significant increase in system cost and, in particular, the cost of system storage space and, although there are techniques to reduce the overhead requirements of such methods, they typically introduce second order behaviors which can negatively affect system performance.
A second approach to storing sharing information is to distribute the sharing information for each line as evenly as possible across all of the nodes sharing the line, typically by requiring each node to store and maintain the sharing information associated with the lines encached in the node. The amount of total cache space in the nodes is typically orders of magnitude smaller than the amount of global memory, so that the number of lines encached in the nodes will be orders of magnitude less than the number of lines in the system global memory. Because of this, these methods thereby minimize the amount of information stored in each home node tag, for which there is one per line of global memory and distribute the remainder of the sharing information across the cache tags maintained by the other nodes sharing the line. In this respect, it will be recognized that the sharing information storage requirements that are thereby imposed on the nodes encaching lines belonging to other nodes is limited because the number of lines that can be encached in a given node is limited. The advantage of these methods is thereby a significant reduction in the overhead storage requirements for sharing information in each home node. The primary disadvantage of these methods is that since the sharing information is no longer co-located, the average latency per transaction is usually greatly increased, thereby significantly reducing system performance.
The present invention provides a solution to these and other problems of the prior art.
The present invention is directed to a method and mechanism for tracking and managing cached data in a multiprocessor system and, in particular, to a cache based vector coherency method and mechanism for tracking and managing data use in a multiprocessor system. In particular, the present invention is directed to a shared line coherency method and mechanism for maintaining coherency of shared lines among the nodes of a system including a plurality of nodes sharing lines of information wherein each line is an element of information.
The shared line coherency mechanism includes a single associated home node for each shared line wherein the home node of a line always contains a copy of the line, may include a plurality of leaf nodes for a given shared line wherein each leaf node shares the line and contains an encached copy of the line, and may include a single associated owner node for a given shared line wherein the owner node shares the line, contains an encached copy of the line, and contains a vector directory identifying the leaf nodes of the line. According to the present invention, all requests directed to a shared line are directed to the home node of the line and a home node receiving a request directed to a shared line will provide a copy of the line to the requesting node and will forward the request to the owner node of the line for completion of the request. The owner node is the first node to access the line, and subsequently the last node to modify the line, and operates to track all leaf nodes of the line and, for this purpose, the vector directory contains an entry for each possible leaf node of the line wherein each entry indicates whether the corresponding node is a leaf node having a valid copy of the line.
Each node maintains a line tag for each line resident in the node, whether the line resides in the node because the node is the home node or whether the node is a leaf node of an owner node of the line. The home node of a line includes the associated line, a line tag representing a current home node state and an identifier of a current node to which the home node is to direct communications and a leaf node of a line includes an encached copy of the line, a line tag representing a current leaf node state, and an identification of a current node to which the leaf node is to direct communications. An owner node of a line includes an encached copy of the line, a line tag representing a current owner node state and a vector directory including an entry corresponding to each possible sharing node of the system and indicating each current leaf node of the line.
The shared line coherency mechanism of the present invention further includes a distributed prepention queue mechanism for ordering concurrently pending requests for access to a line wherein the prepention queue mechanism includes the home node of the line and the prepention queue is distributed across all nodes having a pending request directed to the line. The home node is responsive to a request by a requesting node for access to a line while a preceding request is uncompleted by adding the requesting node to a prepention queue containing at least one preceding node having an uncompleted request for access to the line by directing the requesting node to communicate one or more retry requests to the immediately preceding node in the prepention queue. Each requesting node in the prepention queue responds to placement in the prepention queue by spin looping retry requests against the immediately preceding node until the immediately preceding node exists the prepention queue upon completion of a request by the immediately preceding node. Upon reaching the end of the prepention queue, the requesting node, communicating the next retry request to the owner node and exits the prepention queue upon completion of the request.
The shared line coherency mechanism of the present invention further includes a packet communication mechanism for communicating information pertaining to requests among the nodes wherein a request from a requesting node to another node is communicated in a request packet, a response to a request packet from a node receiving a request packet is communicated to another node in a response packet, and a request from a node receiving a request packet is communicated to a node to which the request packet is directed in a forwarded request packet concurrently with a corresponding response packet to the node originating the request packet.
A request packet includes an identifier of a node to which the request is directed, an identifier of a node sending the packet, an identifier of a node originating the request, a transaction identifier assigned by the node originating the request and identifying the request transaction, an identifier of a target of the request, a command pertaining to the request, and a command qualifier representing a specific requested action. A request packet may also include an identification of possible current leaf nodes of a line that is a target of the request or an identifier of a node to which communications are to be directed.
A response packet includes an identifier of a node to which the response is directed, an identifier of a node which originated a request to which the response packet contains a response, a transaction identifier assigned by the node originating the request and identifying the request transaction, a command, and a command qualifier representing a specific requested action. A response packet may also include an identification of possible current leaf nodes of a line that is a target of the request or an identifier of a node to which communications are to be directed.
A forwarded request packet includes an identifier of a node to which the request is directed, an identifier of a node sending the packet, an identifier of a node originating the request, a transaction identifier assigned by the node originating the request and identifying the request transaction, an identifier of a target of the request, a command pertaining to the request, and a command qualifier representing a specific requested action. A forwarded request packet may also include an identification of possible current leaf nodes of a line that is a target of the request or an identifier of a node to which communications are to be directed.
The present invention includes methods for providing nodes with access to lines, for providing a requesting node with access to a currently unshared line, for providing a requesting node with read access to a currently read shared line, for providing a requesting node with modification access to a currently read shared line, for providing a requesting node with read access to a modified line, for providing a requesting leaf node having an invalidated copy of a modified line with read access to the modified line, for promoting a read access of a requesting node of a read-only encached line to a write access to the line, for promoting a read access of a requesting node to a read-only encached line to a write access in request race conditions, and for evicting a line from a leaf node.
The present invention further includes a shared line coherency mechanism residing in each node participating in line sharing wherein each node includes a processor for performing operations on lines, a memory for storing lines for which the node is the home node, a cache for storing shared lines, and a memory/cache manager for performing memory and cache functions. The shared line coherency mechanism includes a line tag memory for storing a line tag for each line resident in the node, a packet generator and parser for communicating requests and responses to requests pertaining to lines among the nodes of the system, and a coherency controller responsive to line operations of the node and communications pertaining to lines among the nodes of the system and for controlling operation of the memory/cache manager. The line tag associated with a line resident in the node includes a state value representing a state of the line with respect to the node and an identifier of a node relevant to the current state of the line. The state value may represent that the node is the single associated home node of the line and the current state of the line in the line home node, that the node is a leaf node of the line containing an encached copy of the line and the current state of the line in the leaf node, or that the node is a single associated owner node of the line and the state of the line in the line owner node. When the node is the home node or a leaf node of the line, the identifier indicates a current node to which the node is to direct communications pertaining to the line. When the node is the home node of the line, the current node to which the home node is to direct communications is the current owner node of the associated line, when the node is the home node of the line, the current node to which the home node is to direct communications is a node requesting access to the associated line, and when the node is a leaf node of the line, the current node to which the leaf node is to direct communications is a suspected current owner node of the associated line. When the node is the owner node of the line, the identifier is vector directory containing an entry for each possible leaf node of the line and each entry indicates whether the corresponding node is a leaf node contains a valid copy of the line 49. The line tag associated with a line resident in the node may also contain a state value representing that the node is in a prepention queue of pending requests with respect to the line and is to direct retry requests to an immediately preceding node in the prepention queue and an identifier of the immediately preceding node in the prepention queue.
The shared line coherency mechanism of the present invention operates such that all communications that are requests directed to a shared line are directed to the home node of the line and a home node receiving a request directed to a shared line will provide a copy of the line to the requesting node, and will forward the request to the owner node of the line for completion of the request.
The shared line coherency mechanism of the present invention further includes a prepention queue mechanism for ordering pending requests for access to a line wherein the prepention queue mechanism includes the shared line coherency mechanism of the home node of the line and shared line coherency mechanism of each requesting node in the prepention queue. The shared line coherency mechanism of the home node of a line is responsive to a request by a requesting node for access to the line while a preceding request directed to the line is uncompleted by adding the requesting node to a prepention queue containing at least one preceding node having an uncompleted request for access to the line by directing the requesting node to communicate one or more retry requests to the immediately preceding node in the prepention queue. The shared line coherency mechanism of each requesting node in the prepention queue responds to placement of the node in the prepention queue by spin looping retry requests against the immediately preceding node until the immediately preceding node exists the prepention queue upon completion of a request by the immediately preceding node. When the requesting node progresses through the prepention queue to the end of the prepention queue, the shared line coherency mechanism communicates the next retry request to the owner node and exits the prepention queue upon completion of the request.
The shared line coherency mechanism of a home node adds a requesting node to a prepention queue by communicating to the requesting node a response including an identifier of the immediately preceding node in the prepention queue and an indication that the requesting queue is to enter the prepention queue and the shared line coherency mechanism of the requesting node responds to the home node of the line by writing the identification of the immediately preceding node in the prepention queue into the identifier of the line tag corresponding to the line and writing a state value indicating that the requesting node is to communicate a retry request to the node identified by the identifier. The shared line coherency mechanism of the requesting node responds to completion of the request by writing the identification of the home node of the line into the identifier of the line tag corresponding to the line and writing a state value representing the current state of the line in the requesting node into the state value of the line tag corresponding to the line.